This invention relates to digital comparators, and particularly to comparators for use in very large scale integrated circuits (VLSI circuits).
Comparators are widely used in VLSI circuits, and are one of the most commonly used datapath modules in application specific integrated circuits (ASICs). The performance of the implemented comparator highly affects the quality of the VLSI circuit, and its timing closure.
Prior digital comparators have employed an architecture based on AND and OR elements. One such circuit, known as a dichotomizing circuit, achieves a circuit depth of 2 logxe2x80x942n+O(1) and a complexity of 3nxe2x88x92O(logxe2x80x942n), where n is the number of bits of the comparator. While the complexity of such comparators is minimally acceptable, the depth, and hence the time delay, is large.
The present invention is directed to a comparator architecture based on a Fibonacci series that provides an approach to the design of comparators based on the global analysis of their Boolean identities. The resulting comparators have smaller depth and time delay. In some cases, circuit area is reduced.
In accordance with the present invention a comparator is embodied in an integrated circuit and is characterized by an architecture having output functions h_n and v_n that depend from input functions U[i]=AND(NOT(A[i]), B[i]) and V[i]=OR(NOT(A[i]), B[i]), where A[i] and B[i] are inputs to the comparator, and functions h_n, v_n are defined as                     h_n        =                  xe2x80x83                ⁢                  h_n          ⁢                      xe2x80x83                    ⁢                      (                                          U                ⁡                                  [                  0                  ]                                            ,                              U                ⁡                                  [                  1                  ]                                            ,                              V                ⁡                                  [                  1                  ]                                            ,              …              ⁢                              xe2x80x83                            ,                              U                ⁡                                  [                                      n                    -                    1                                    ]                                            ,                              V                ⁡                                  [                                      n                    -                    1                                    ]                                                      )                                                  =                  xe2x80x83                ⁢                  OR          ⁢                      xe2x80x83                    ⁢                      (                                          U                ⁡                                  [                                      n                    -                    1                                    ]                                            ,                              AND                ⁢                                  xe2x80x83                                ⁢                                  (                                                            V                      ⁡                                              [                                                  n                          -                          1                                                ]                                                              ,                                          U                      ⁡                                              [                                                  n                          -                          2                                                ]                                                                              )                                            ,              …              ⁢                              xe2x80x83                            ,              AND                                                                                    xe2x80x83                    ⁢                      (                                          V                ⁡                                  [                                      n                    -                    1                                    ]                                            ,              …              ⁢                              xe2x80x83                            ,                              V                ⁡                                  [                  1                  ]                                            ,                              U                ⁡                                  [                  0                  ]                                                      )                    )                ,        and                                v_n        =                  xe2x80x83                ⁢                  v_n          ⁢                      xe2x80x83                    ⁢                      (                                          V                ⁡                                  [                  0                  ]                                            ,              …              ⁢                              xe2x80x83                            ,                              V                ⁡                                  [                                      n                    -                    1                                    ]                                                      )                                                  =                  xe2x80x83                ⁢                  AND          ⁢                      xe2x80x83                    ⁢                                    (                                                V                  ⁡                                      [                    0                    ]                                                  ,                …                ⁢                                  xe2x80x83                                ,                                  V                  ⁡                                      [                                          n                      -                      1                                        ]                                                              )                        .                              
The comparator is further characterized by a minimal depth defined by a recursive expansion of functions h_n=OR(h_k, AND(v_k, h_{nxe2x88x92k})) and v_n=AND(v_k, v{nxe2x88x92k}), where k=F_l and nxe2x88x92k=F_{lxe2x88x921}, l satisfies F_l less than n=F_{l+1}, where {F_l} is a Fibonacci series and n is the number of bits of an input to the comparator.
In some embodiments, a distribution of negations of modules of the comparator is optimized. A set of delay vectors is identified and recursively compared to derive a set of minimum vectors. A vector having a minimum norm is selected from the set of minimum vectors.
The comparator is characterized by the use of logic elements having a function OR(NOT(a),b) instead of EXCLUSIVE OR functions. In some embodiments, the comparator is further characterized by the inclusion of OR logical functions in place of NOR functions and AND logical functions in place of NAND functions.
In some embodiments, a LEQ flag is input to the comparator to signify strict or non-strict comparison of the input numbers.
In some embodiments, the comparator is constructed using 2-input elements mapped from 3-input elements in a library. In other embodiments, the comparator is constructed using 4-input elements constructed from 2-input elements. In other embodiments, the comparator is constructed having six outputs.
In other embodiments, the invention is manifest in a computer readable program containing code that, when executed by a computer, causes the computer to perform the process steps to design a comparator for an integrated circuit based on a Fibonacci series and employing 2-input elements of minimal depth.